<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>1234. 替换子串得到平衡字符串</title>
  </head>
  <body>
    <script>
      //     有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

      // 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

      //

      // 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

      // 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

      // 请返回待替换子串的最小可能长度。

      // 如果原字符串自身就是一个平衡字符串，则返回 0。

      //

      // 示例 1：

      // 输入：s = "QWER"
      // 输出：0
      // 解释：s 已经是平衡的了。
      // 示例 2：

      // 输入：s = "QQWE"
      // 输出：1
      // 解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
      // 示例 3：

      // 输入：s = "QQQW"
      // 输出：2
      // 解释：我们可以把前面的 "QQ" 替换成 "ER"。
      // 示例 4：

      // 输入：s = "QQQQ"
      // 输出：3
      // 解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
      //

      // 提示：

      // 1 <= s.length <= 10^5
      // s.length 是 4 的倍数
      // s 中只含有 'Q', 'W', 'E', 'R' 四种字符

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/replace-the-substring-for-balanced-string
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
      /**
       * @param {string} s
       * @return {number}
       */
      var balancedString = function (s) {
        //核心思路就是找多余的字母，字母数目超出平均值的就是多余字母
        let initial = { Q: 0, W: 0, E: 0, R: 0 }
        for (const char of s) {
          initial[char]++
        }
        let count = 0
        const aver = s.length / 4
        //计算count，即多余的字母
        for (const item in initial) {
          if (initial[item] > aver) {
            initial[item] -= aver
            count += initial[item]
          } else {
            initial[item] = 0
          }
        }
        if (count === 0) {
          return 0
        }
        let l = 0,
          r = 0
        let res = Infinity
        while (r < s.length) {
          //如果initial的该字母大于0，说明是多余字母，count--
          if (initial[s[r]] > 0) {
            count--
          }
          initial[s[r]]--
          //说明找到了所有的多余字母
          if (count === 0) {
            //l左移，先把正常字母去掉
            while (initial[s[l]] < 0) {
              initial[s[l]]++
              l++
            }
            //比较最小值
            res = Math.min(res, r - l + 1)
            //破坏平衡，关键，l右移保证count又会大于0（因为上面l右移到 恰好满足这个字母等于0的位置）
            //无论是多余的字母，还是正常字母，都只能移到到initial[character]===0的位置来确保夹在l和r里面的区间能最少覆盖所有多余字母
            initial[s[l]]++
            l++
            count++
          }
          //正常的右移，1.写for循环，2.写r<s.length都行
          r++
        }
        return res
      }
    </script>
  </body>
</html>
